package com.njupt.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/12 10:26
 * @Description: 216. 组合总和 III
 * @Version: 1.0
 */


public class CombinationSum3 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> result = new LinkedList<>();
        int sum = 0;
        int startIndex = 1;
        backTracking(k,n,results,result,sum,startIndex);
        return results;
    }

    private void backTracking(int k, int n, List<List<Integer>> results, List<Integer> result, int sum,int startIndex) {
        if(result.size() == k){
            if(sum == n){
                results.add(new ArrayList(result));
            }
            return;
        }
        for (int i = startIndex; i <=9 ; i++) {
            sum += i;
            result.add(i);
            backTracking(k,n,results,result,sum,i+1);
            sum -= i;
            result.remove(result.size()-1);
        }
    }

    public static void main(String[] args) {
        CombinationSum3 test = new CombinationSum3();
        List<List<Integer>> lists = test.combinationSum3(3, 9);
        System.out.println(lists);
    }
}
